class Solution
{
    int row, col;
public:
    int cutOffTree(vector<vector<int>>& forest)
    {
        int ret = 0;
        row = forest.size(), col = forest[0].size();
        vector<pair<int, int>> flag;
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (forest[i][j] > 1)
                {
                    flag.push_back({ i,j });
                }
            }
        }
        sort(flag.begin(), flag.end(), [&](const pair<int, int>& px, const pair<int, int>& py)
            {
                return forest[px.first][px.second] < forest[py.first][py.second];
            });
        int sx = 0, sy = 0;
        for (auto& [a, b] : flag)
        {
            int ex = a, ey = b;
            int step = BFS(forest, sx, sy, ex, ey);
            if (step == -1) return -1;
            ret += step;
            sx = a, sy = b;
        }
        return ret;
    }
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    bool check[51][51];
    int BFS(vector<vector<int>> forest, int sx, int sy, int ex, int ey)
    {
        if (sx == ex && sy == ey) return 0;
        int step = 0;
        memset(check, false, sizeof check);
        queue<pair<int, int>> q1;
        q1.push({ sx,sy });
        while (q1.size())
        {
            ++step;
            int sz = q1.size();
            for (int i = 0; i < sz; i++)
            {
                auto [a, b] = q1.front();
                q1.pop();
                for (int k = 0; k < 4; k++)
                {
                    int x = a + dx[k], y = b + dy[k];
                    if (x >= 0 && x < row && y >= 0 && y < col && forest[x][y] != 0 && !check[x][y])
                    {
                        if (x == ex && y == ey) return step;
                        q1.push({ x,y });
                        check[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }
};